package com.data.algorithm.Josephus;

import lombok.Getter;
import lombok.Setter;
import lombok.extern.slf4j.Slf4j;

/**
 * 约瑟夫问题--环形单链表实现
 *
 * @author wangjie
 * @version V1.0
 * @date 2019/12/27
 */
public class JosepfuDemo {

    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(41);
        circleSingleLinkedList.show();
        circleSingleLinkedList.start(1,3);
        circleSingleLinkedList.show();
    }

}

/**
 * 环形单链表
 *
 * @author wangjie
 * @version V1.0
 * @date 2019/12/27
 */
@Slf4j
class CircleSingleLinkedList{

    /**
     * 头结点
     */
    private Node head;
    /**
     * 节点数
     */
    private int num;
    /**
     * 构建环形链表
     * @param num
     */
    public CircleSingleLinkedList(int num){

        if(1 > num ){
            log.info("【环形链表初始值不能小于1】");
            return;
        }

        this.num = num;
        Node pointer = null;

        for(int i = 1;i <= num;i++){
           Node node = new Node(i);
           if (1 == i){
               head = node;
               pointer = node;
               pointer.next = node;
           }else{
               pointer.next = node;
               node.next = head;
               pointer = node;
           }
        }

    }

    /**
     * 遍历
     */
    public void show(){
        log.info("-------------------------------开始遍历--------------------------------");
        if(null == head){
            log.info("【环形链表为空】");
            return;
        }
        Node pointer = head;
        do{
            log.info("节点编号：{}",pointer.getNo());
            pointer = pointer.next;
        } while (pointer != head);
        log.info("-------------------------------遍历完成--------------------------------");
    }

    /**
     * 开始游戏
     * @param start 从第几个开始数
     * @param no 数多少
     */
    public void start(int start,int no){

        if(null == head || start > num){
            log.info("【参数有误！】");
            return;
        }
        log.info("--------------开始游戏，总人数{}，从第{}人开始数，数到{}的人出局------------",num,start,no);
        Node help = head;
        Node pointer = head;
        while (help.next != head){
            help = help.next;
        }
        //头结点置为空
        head = null;
        for (int i = 1;i < start;i++){
            pointer = pointer.next;
            help = help.next;
        }
        while (pointer != help){
            for (int i = 1;i < no;i++){
                pointer = pointer.next;
                help = help.next;
            }
            log.info("{}号出局",pointer.getNo());
            pointer = pointer.next;
            help.next =pointer;
        }
        log.info("-------------------------------游戏结束--------------------------------");
        log.info("{}号胜出",pointer.getNo());
    }
}
/**
 * 链表结点
 *
 * @author wangjie
 * @version V1.0
 * @date 2019/12/27
 */
@Setter
@Getter
class Node{
    /**
     * 编号
     */
    private int no;
    /**
     * 指向下一个结点
     */
    public Node next;

    public Node(int no){
        this.no = no;
    }

}

